package com.le.enhance.class5;

import org.junit.Test;

/**
 * 给定两个结点,寻找这两个结点的最低公共祖先
 * 分析: 给定结点为a,b
 * 1. a是b的的最低公共祖先, 或者b是a的最低公共祖先
 * 2. 公共祖先为别人
 */
public class Code_07_lowestCommonAncestors {

    public static class Node {
        public int val;
        Node left;
        Node right;

        public Node(int val) {
            this.val = val;
        }
    }

    public static Node process(Node head, Node a, Node b) {
        if (head == null || head == a || head == b) {
            return head;
        }
        Node leftInfo = process(head.left, a, b);
        Node rightInfo = process(head.right, a, b);
        // head 是二者的最低公共结点
        if (leftInfo != null && rightInfo != null) {
            return head;
        }
        return leftInfo != null ? leftInfo : rightInfo;
    }
    
    @Test
    public void test(){
        Node head = new Node(4);
        head.left = new Node(2);
        head.right = new Node(6);
        head.left.left = new Node(1);
        head.left.right = new Node(3);
        head.right.left = new Node(7);
        System.out.println(process(head,head.left.left,head.right.right).val);
    }
}
